#ifndef __LINKLIST_H_
#define __LINKLIST_H_
#include<iostream>
#include "DynamicArra.h"

class LinkList
{
public:
    using ElementType = int;
    LinkList();
    //插入
    void InsertHead(const ElementType& element);
    void InsertByIndex(int index, const ElementType element);
    void InsertTail(const ElementType& element);
    
    //删除
    void RemoveByIndex(int index);
    void RemoveByElement(const ElementType& element);

    //按位置查找
    ElementType* FindByIndex(int index);
    //按值查找：指向数据域的指针，为了能全部找到，使用数组存储指针
    DynamicArray FindByElement(const ElementType& element);

    //排序
    void BubbleSort();
    //快速排序
    void Sort();
    
    //链表逆序:非递归
    void Reserve();
    //递归逆序
    void Reserve2();

    void show();
    ~LinkList();

private:
    struct Node //链表的结点
    {
        Node(const ElementType& data):data(data),next(nullptr){}
        ElementType data; // 数据域
        Node *next; //指针域
    };
    
    void FastSort(Node *start, Node *end);
    Node *Reserve2(Node *node);
    Node *head;
    int size; //元素个数
};







#endif